◀ Prev · Parts · Full · Next ▶

The input graph G ( V , E ) {\displaystyle G(V,E)} is considered to be a network, where vertices V {\displaystyle V} are independent computing nodes and edges E {\displaystyle E} are communication links. Links are weighted as in the classical problem.

At the beginning of the algorithm, nodes know only the weights of the links which are connected to them. (It is possible to consider models in which they know more, for example their neighbors' links.)

As the output of the algorithm, every node knows which of its links belong to the minimum spanning tree and which do not.

The message-passing model is one of the most commonly used models in distributed computing. In this model, each process is modeled as a node of a graph. Each communication channel between two processes is an edge of the graph.

Two commonly used algorithms for the classical minimum spanning tree problem are Prim's algorithm and Kruskal's algorithm. However, it is difficult to apply these two algorithms in the distributed message-passing model. The main challenges are:

• Both Prim's algorithm and Kruskal's algorithm require processing one node or vertex at a time, making it difficult to make them run in parallel. For example, Kruskal's algorithm processes edges in turn, deciding whether to include the edge in the MST based on whether it would form a cycle with all previously chosen edges.

◀ Prev · Parts · Full · Next ▶